package com.example.leetcode.trainingcamp.week7.Thursday;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/** 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。 */
public class Offer04_03 {

    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) return new ListNode[0];
        Queue<TreeNode> queue = new LinkedList<>();
        List<ListNode> list = new ArrayList<>();
        queue.add(tree);
        while (!queue.isEmpty()){
            int size = queue.size();
            ListNode head = new ListNode(0);
            ListNode tail = head;
            for (int i = 0;i<size;i++){
                TreeNode poll = queue.poll();
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
                ListNode listNode = new ListNode(poll.val);
                tail.next = listNode;
                tail = listNode;
            }
            list.add(head.next);
        }
        ListNode[] result = new ListNode[list.size()];
        for (int i = 0;i<list.size();i++){
            result[i] = list.get(i);
        }
        return result;
    }
}





class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}



